package code.map;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: HandWriteSourceCode 手写hashmap
 * @description 手写HashMap
 **/
public class MyHashMap<K, V> implements MyMap<K, V> {

    //默认长度容量
    private int defaultLength = 16;

    //默认负载因子
    private double defaultAddFactor = 0.75;

    //使用数组位置的数量
    private int useSize;

    //数组
    private MyHashMapEntry<K, V>[] table;

    //默认构造函数
    public MyHashMap() {
        this(16, 0.75);
    }

    public MyHashMap(int defaultLength, double defaultAddFactor) {
        if (defaultLength < 0) {
            throw new IllegalArgumentException("数组异常");
        }
        if (defaultAddFactor <= 0 || Double.isNaN(defaultAddFactor)) {
            throw new IllegalArgumentException("因子异常");
        }
        this.defaultLength = defaultLength;
        this.defaultAddFactor = defaultAddFactor;
        this.table = new MyHashMapEntry[defaultLength];
    }

    @Override
    public V get(K k) {
        //计算出下标
        int index = getIndex(k, table.length);
        MyHashMapEntry<K, V> entry = table[index];
        if (entry == null){
            throw new NullPointerException();
        }
        while (entry != null){
            if (k == entry.getKey() || k.equals(entry.getKey())) {
                return entry.v;
            }else {
                entry = entry.next;
            }
        }
        return null;
    }

    @Override
    public V put(K k, V v) {
        //判断是否要扩容
        if (useSize > table.length * defaultAddFactor){
            resize();
        }
        //计算出下标
        int index = getIndex(k, table.length);
        MyHashMapEntry<K, V> entry = table[index];
        MyHashMapEntry<K, V> newEntry = new MyHashMapEntry<>(k, v, null);
        if (entry == null){
            table[index] = newEntry;
            useSize++;//table中有位置被占
        }else {
            MyHashMapEntry<K, V> t = entry;
            if (t.getKey() == k || (t.getKey() != null && t.getKey().equals(k))){
                //相同的key 设置值
                t.v = v;
            }else {
                while (t.next != null){
                    if (t.getKey() == k || (t.getKey() != null && t.getKey().equals(k))){
                        //相同的key 设置值
                        t.v = v;
                        break;
                    }else{
                        t = t.next;
                    }
                }
                if (t.next == null){
                    t.next = newEntry;
                }
            }
        }
        return newEntry.getValue();
    }


    /**
     * 扩容方法
     */
    private void resize() {
        MyHashMapEntry<K, V>[] newTable = new MyHashMapEntry[defaultLength * 2];
        List<MyHashMapEntry<K, V>> list = new ArrayList<>();
        for (int i = 0; i < table.length; i++){
            MyHashMapEntry<K, V> entry = table[i];
            if (entry == null){
                continue;
            }
            while (entry != null){
                list.add(entry);
                entry = entry.next;
            }
        }
        if (list.size() > 0){
            useSize = 0;
            defaultLength = defaultLength * 2;
            table = newTable;
            for (MyHashMapEntry<K, V> entry : list) {
                if (entry.next != null){
                    entry.next = null;
                }
                this.put(entry.k, entry.v);
            }
        }
    }

    @Override
    public int size() {
        return 0;
    }

    /**
     * 获取保存位置的数组下标
     *
     * @param k
     * @param length
     * @return
     */
    private int getIndex(K k, int length){
        int m = length - 1;
        int index = k.hashCode() % m;
        return index >= 0 ? index : -index;

//        int index = hash(k.hashCode()) & m;//取模
//        return index >= 0 ? index : -index;
    }

    /**
     * 使用每个object的hashCode计算hashCode
     *
     * @param hashCode
     * @return
     */
    private int hash(int hashCode) {
        hashCode = hashCode ^ ((hashCode >>> 20) ^ (hashCode >>> 12));
        return hashCode ^ ((hashCode >>> 7) ^ hashCode >>> 4);
    }

    //HashMap是通过数组+链表，所以这边的节点是链表中的节点，存在next指向下一个节点。
    public class MyHashMapEntry<K, V> implements MyEntry<K, V> {
        K k;
        V v;
        MyHashMapEntry<K, V> next;

        public MyHashMapEntry(K k, V v, MyHashMapEntry<K, V> next) {
            this.k = k;
            this.v = v;
            this.next = next;
        }

        @Override
        public K getKey() {
            return k;
        }

        @Override
        public V getValue() {
            return v;
        }
    }


    public static void main(String[] args) {
        MyHashMap<Integer, String> map = new MyHashMap<>();
        map.put(1, "1");
        System.out.println(map.get(1));
        map.put(2, "2");
        map.put(3, "3");
        map.put(4, "4");
        System.out.println(map.get(2));
        System.out.println(map.get(3));
        System.out.println(map.get(4));
        map.put(4, "4");
        map.put(5, "5");
        map.put(6, "6");
        map.put(7, "7");
        map.put(8, "8");
        map.put(9, "9");
        map.put(10, "10");
        map.put(11, "11");
        map.put(12, "12");
        map.put(13, "13");
        map.put(14, "14");
        map.put(15, "15");
        map.put(16, "16");
        map.put(17, "17");
        System.out.println(map.get(14));
        System.out.println(map.get(15));
        System.out.println(map.get(16));
        System.out.println(map.get(17));
    }

}

